Multicasting is defined as a communication involving one or more senders and receivers. Information transmitted by any participant in the multicast is received by every other participant in the multicast. Users connected to the network who are not participants in a particular multicast do not receive the information transmitted by any of the senders who are participants in the multicast and no network components (e.g. switches and trunks) are used unless actually needed for the multicast. In this sense broadcast (one sender, many receivers) is a special case of multicasting. Possible applications of multicasting include wide-area broadcast (T V. and radio). narrowcast (small area broadcast) and conferencing (small numbers of transmitters and receivers across a wide area).
A telecommunications network may comprise a set of packet switches interconnected by trunks. Illustratively, each switch comprises a switch fabric and is controlled by a route controller, which may be a stored program computing machine or may be a specially dedicated piece of hardware. Such switches are typically used to route data packets from one user in the network to one or more other users. The route controller controls the routing of the data packets through its switch fabric. Thus, the switches serve as cross-connects for a group of trunks. A data packet enters a switch on one trunk and leaves on another trunk.
A packet switch may be centralized or it may be distributed over a large area. An example of a system which forms a distributed packet switch is Ethernet. Thus, the packet switching network may alternately be viewed as a system comprising interconnected subnetworks, wherein each subnetwork may be viewed as a distributed packet switch.
One particular algorithm for routing packets in a packet switching network is disclosed in Kempf U.S. Pat. No. 4,597,078. In the system described in the Kempf patent, packets arrive at packet switches from hosts by way of trunks. Each packet includes a source address, a destination address, and some data. Each switch maintains a table whose entries each include an address and trunk identification number. Upon reception of a packet at a switch, the source address contained in the packet and the identification number of the trunk on which the packet arrived are stored as an entry in the table, unless the table already includes an entry comprising this address and trunk identification number.
Each arriving packet is then routed in one of two ways. If the destination address contained in the packet appears in a table entry as the source address of an earlier packet, the packet is retransmitted on the trunk associated with the remembered source address. If the destination address has never been seen as a source address in a previous packet, the packet is broadcast over all of the trunks connected to the switch, but not over trunk from which it was received.
This algorithm works when the network includes only one possible path between any pair of hosts (i.e. users). This means that the network comprises only a single spanning tree. A more complex network may be handled by decomposing the network into a multiplicity of spanning trees and marking each packet as traveling on a particular spanning tree. The table maintained at each packet switch is expanded to include a spanning tree number for each entry. The multiple spanning tree version of the algorithm is discussed in detail in W. D. Sincoskie U.S. Pat. application Ser. No. 769,555, filed on Aug. 26, 1985, and assigned to the assignee hereof. This patent application is incorporated herein by reference.
However, the algorithms disclosed in the above-identified references are not suitable for routing packets among the participants of a multicast. Accordingly, it is an object of the present invention to provide an algorithm for routing packets among the participants of a multicast.